using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Runtime.CompilerServices;
using System.Text;
using System.Threading.Tasks;

namespace BepuUtilities.Collections
{

    public static class MSBRadixSort
    {
        // TODO：如果JIT曾经设法以最佳方式处理ISPAN索引器,我们可以使用更自然的基于ISPAN的实现。
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        static void Swap<T>(ref T a, ref T b)
        {
            var temp = a;
            a = b;
            b = temp;
        }

        public static void SortU32<T>(ref int keys, ref T values, ref int bucketCounts, ref int bucketOriginalStartIndices, int keyCount, int shift)
        {
            if (keyCount < 32)
            {
                // 剩下的钥匙不多了。使用插入排序。
                for (int i = 1; i < keyCount; ++i)
                {
                    var originalKey = Unsafe.Add(ref keys, i);
                    var originalValue = Unsafe.Add(ref values, i);
                    int compareIndex;
                    for (compareIndex = i - 1; compareIndex >= 0; --compareIndex)
                    {
                        if (originalKey < Unsafe.Add(ref keys, compareIndex))
                        {
                            // 将元素上移一个插槽。
                            var upperSlotIndex = compareIndex + 1;
                            Unsafe.Add(ref keys, upperSlotIndex) = Unsafe.Add(ref keys, compareIndex);
                            Unsafe.Add(ref values, upperSlotIndex) = Unsafe.Add(ref values, compareIndex);
                        }
                        else
                            break;
                    }
                    var targetIndex = compareIndex + 1;
                    if (targetIndex != i)
                    {
                        // 将原始索引下移。
                        Unsafe.Add(ref keys, targetIndex) = originalKey;
                        Unsafe.Add(ref values, targetIndex) = originalValue;
                    }
                }
                return;
            }
            const int bucketCount = 256;
            // bucketCounts的每个部分覆盖256个槽,表示一个字节的所有可能值。
            // 传入根函数的bucketCounts数组必须包含足够的空间来容纳递归的每一级,对于32位排序,最多有1024个条目。
            // 请注意,我们必须清除此处的存储桶,因为前面的值不能保证为零。
            // 待办事项：如果能快点做就好了。光靠裁判是很难做到的,但是如果我们有更多关于数据源的信息,我们可以做initblock之类的事情。
            for (int i = 0; i < bucketCount; ++i)
            {
                Unsafe.Add(ref bucketCounts, i) = 0;
            }
            for (int i = 0; i < keyCount; ++i)
            {
                var key = Unsafe.Add(ref keys, i);
                ++Unsafe.Add(ref bucketCounts, (key >> shift) & 0xFF);
            }

            // 将存储桶计数转换为部分和。
            int sum = 0;
            for (int i = 0; i < bucketCount; ++i)
            {
                var previousSum = sum;
                ref var bucketSlotCount = ref Unsafe.Add(ref bucketCounts, i);
                sum += bucketSlotCount;
                // 我们将部分和存储到bucketCounts数组和OriginalStartIndices数组中。
                Unsafe.Add(ref bucketOriginalStartIndices, i) = previousSum;
                bucketSlotCount = previousSum;
            }

            // 请注意,bucketCounts数组现在实际上是一个startIndices数组。我们将在执行交换时递增数组的bucketCounts版本。
            // 遍历数组中每个存储桶的区域,并遍历每个存储桶中的每个元素。对于每个元素,将其推送到目标存储桶。
            // 不是将移位的元素写入本地存储桶,而是检查它应该放到哪里。重复此操作,直到找到适合当前存储桶的元素。
            // 只有在找到装配元素后,才应将任何内容写入本地铲斗槽。请注意,计数阶段可确保找到元素。
            // 每次写入目标存储桶都应该增加该存储桶的起始索引。
            // 当访问的元素数量达到桶的大小时,移到下一个桶并重新开始。
            for (int i = 0; i < bucketCount; ++i)
            {
                ref var bucketStartIndex = ref Unsafe.Add(ref bucketCounts, i);
                // 请注意原始起始索引的使用。如果它继续超出原来的起点,它将走进一个已经排序的区域。
                int nextStartIndex = i == bucketCount - 1 ? keyCount : Unsafe.Add(ref bucketOriginalStartIndices, i + 1);
                while (bucketStartIndex < nextStartIndex)
                {
                    var localKey = Unsafe.Add(ref keys, bucketStartIndex);
                    var localValue = Unsafe.Add(ref values, bucketStartIndex);
                    while (true)
                    {
                        var targetBucketIndex = (localKey >> shift) & 0xFF;
                        if (targetBucketIndex == i)
                        {
                            // 本地密钥属于本地存储桶。我们可以停止掉期。
                            // 将本地密钥放入本地存储桶中。
                            Unsafe.Add(ref keys, bucketStartIndex) = localKey;
                            Unsafe.Add(ref values, bucketStartIndex) = localValue;
                            ++bucketStartIndex;
                            break;
                        }
                        ref var targetBucketStartIndex = ref Unsafe.Add(ref bucketCounts, targetBucketIndex);
                        Debug.Assert((targetBucketIndex < 255 && targetBucketStartIndex < Unsafe.Add(ref bucketCounts, targetBucketIndex + 1)) ||
                            (targetBucketIndex == 255 && targetBucketStartIndex < keyCount));
                        ref var targetKeySlot = ref Unsafe.Add(ref keys, targetBucketStartIndex);
                        ref var targetValueSlot = ref Unsafe.Add(ref values, targetBucketStartIndex);
                        Swap(ref targetKeySlot, ref localKey);
                        Swap(ref targetValueSlot, ref localValue);
                        ++targetBucketStartIndex;
                    }
                }
            }


            // 现在每个存储桶都包含属于它的元素。可能仍有分类工作要做。
            if (shift > 0)
            {
                // 可能还需要至少多一个级别的排序。
                var newShift = shift - 8;
                ref var nextLevelBucketCounts = ref Unsafe.Add(ref bucketCounts, bucketCount);

                var previousEnd = 0;
                for (int i = 0; i < bucketCount; ++i)
                {
                    var bucketEnd = Unsafe.Add(ref bucketCounts, i);
                    var count = bucketEnd - previousEnd;
                    if (count > 0)
                        SortU32(ref Unsafe.Add(ref keys, previousEnd), ref Unsafe.Add(ref values, previousEnd), ref nextLevelBucketCounts, ref bucketOriginalStartIndices, count, newShift);
                    previousEnd = bucketEnd;
                }
            }
        }





        public unsafe static void SortU32<T>(ref int keys, ref T values, int keyCount, int shift)
        {
            if (keyCount < 256)
            {
                var comparer = default(PrimitiveComparer<int>);
                QuickSort.Sort(ref keys, ref values, 0, keyCount - 1, ref comparer);
                return;
            }
            const int bucketCountPower = 7;
            const int bucketCount = 1 << bucketCountPower;
            const int mask = bucketCount - 1;
            // 这个stackalloc实际上并不是非常快-默认行为是将范围清零。但我们实际上想把它归零,所以这没问题。
            var bucketCounts = stackalloc int[bucketCount];
#if RELEASESTRIP
            Unsafe.InitBlockUnaligned(bucketCounts, 0, sizeof(int) * bucketCount);
#endif
#if DEBUG
            for (int i = 0; i < bucketCount; ++i)
            {
                Debug.Assert(bucketCounts[i] == 0,
                    "It's really, really unlikely that they would choose to change the stackalloc init behavior without requiring an attribute or something, " +
                    "but if they do, everything breaks. If this ever gets hit, use Unsafe.InitBlock or similar.");
            }
#endif
            for (int i = 0; i < keyCount; ++i)
            {
                var key = Unsafe.Add(ref keys, i);
                ++bucketCounts[(key >> shift) & mask];
            }

            // 与bucketCounts不同,我们不想预初始化这些起始索引。
            // 但不管我们喜欢与否,他们都会是这样的。(除非编译器意识到不可能读取未初始化的值,但祝您好运。)
            // 因此,对此使用较大的存储桶计数并不理想。如果您想要更大的存储桶大小,在调用外部预分配内存是个好主意。
            var bucketOriginalStartIndices = stackalloc int[bucketCount];
            // 将存储桶计数转换为部分和。
            int sum = 0;
            for (int i = 0; i < bucketCount; ++i)
            {
                var previousSum = sum;
                ref var bucketSlotCount = ref bucketCounts[i];
                sum += bucketSlotCount;
                // 我们将部分和存储到bucketCounts数组和OriginalStartIndices数组中。
                bucketOriginalStartIndices[i] = previousSum;
                bucketSlotCount = previousSum;
            }

            // 请注意,bucketCounts数组现在实际上是一个startIndices数组。我们将在执行交换时递增数组的bucketCounts版本。
            // 遍历数组中每个存储桶的区域,并遍历每个存储桶中的每个元素。对于每个元素,将其推送到目标存储桶。
            // 不是将移位的元素写入本地存储桶,而是检查它应该放到哪里。重复此操作,直到找到适合当前存储桶的元素。
            // 只有在找到装配元素后,才应将任何内容写入本地铲斗槽。请注意,计数阶段可确保找到元素。
            // 每次写入目标存储桶都应该增加该存储桶的起始索引。
            // 当访问的元素数量达到桶的大小时,移到下一个桶并重新开始。
            for (int i = 0; i < bucketCount; ++i)
            {
                ref var bucketStartIndex = ref bucketCounts[i];
                // 请注意原始起始索引的使用。如果它继续超出原来的起点,它将走进一个已经排序的区域。
                int nextStartIndex = i == bucketCount - 1 ? keyCount : bucketOriginalStartIndices[i + 1];
                while (bucketStartIndex < nextStartIndex)
                {
                    var localKey = Unsafe.Add(ref keys, bucketStartIndex);
                    var localValue = Unsafe.Add(ref values, bucketStartIndex);
                    while (true)
                    {
                        var targetBucketIndex = (localKey >> shift) & mask;
                        if (targetBucketIndex == i)
                        {
                            // 本地密钥属于本地存储桶。我们可以停止掉期。
                            // 将本地密钥放入本地存储桶中。
                            Unsafe.Add(ref keys, bucketStartIndex) = localKey;
                            Unsafe.Add(ref values, bucketStartIndex) = localValue;
                            ++bucketStartIndex;
                            break;
                        }
                        ref var targetBucketStartIndex = ref bucketCounts[targetBucketIndex];
                        Debug.Assert((targetBucketIndex < bucketCount - 1 && targetBucketStartIndex < bucketCounts[targetBucketIndex + 1]) ||
                            (targetBucketIndex == bucketCount - 1 && targetBucketStartIndex < keyCount));
                        ref var targetKeySlot = ref Unsafe.Add(ref keys, targetBucketStartIndex);
                        ref var targetValueSlot = ref Unsafe.Add(ref values, targetBucketStartIndex);
                        Swap(ref targetKeySlot, ref localKey);
                        Swap(ref targetValueSlot, ref localValue);
                        ++targetBucketStartIndex;
                    }
                }
            }


            // 现在每个存储桶都包含属于它的元素。可能仍有分类工作要做。
            if (shift > 0)
            {
                // 可能还需要至少多一个级别的排序。
                var newShift = Math.Max(0, shift - bucketCountPower);

                var previousEnd = 0;
                for (int i = 0; i < bucketCount; ++i)
                {
                    var bucketEnd = bucketCounts[i];
                    var count = bucketEnd - previousEnd;
                    if (count > 0)
                        SortU32(ref Unsafe.Add(ref keys, previousEnd), ref Unsafe.Add(ref values, previousEnd), count, newShift);
                    previousEnd = bucketEnd;
                }
            }
        }

    }
}
